The order of the giant component of random hypergraphs

We establish central and local limit theorems for the number of vertices in the largest component of a random d‐uniform hypergraph H_d(n,p) with edge probability p = c/ , where c > (d ‐ 1)^‐1 is a constant. The proof relies on a new, purely probabilistic approach. © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2010     

Rainbow and orthogonal paths in factorizations of Kn

For n even, a factorization of a complete graph K_n is a partition of the edges into n?1 perfect matchings, called the factors of the factorization. With respect to a factorization, a path is called rainbow if its edges are from distinct factors. A rainbow Hamiltonian path takes exactly one edge from each factor and is called orthogonal to the factorization. It is known that not all factorizations have orthogonal paths. Assisted by a simple edge‐switching algorithm, here we show that for n?8, the rotational factorization of K_n, GK_n has orthogonal paths. We prove that this algorithm finds a rainbow path with at least (2n+1)/3 vertices in any factorization of K_n (in fact, in any proper coloring of K_n). We also give some problems and conjectures about the properties of the algorithm. © 2010 Wiley Periodicals, Inc. J Combin Designs 18: 167–176, 2010     

Explicit sparse almost‐universal graphs for ${\bf {{\cal G}(n, {k \over n})}}$

For any integer n, let be a probability distribution on the family of graphs on n vertices (where every such graph has nonzero probability associated with it). A graph Γ is ‐almost‐universal if Γ satisifies the following: If G is chosen according to the probability distribution , then G is isomorphic to a subgraph of Γ with probability 1 ‐ . For any p ∈ [0,1], let (n,p) denote the probability distribution on the family of graphs on n vertices, where two vertices u and v form an edge with probability p, and the events {u and v form an edge}; u,v ∈ V (G) are mutually independent. For k ≥ 4 and n sufficiently large we construct a ‐almost‐universal‐graph on n vertices and with O(n)polylog(n) edges, where q = ? ? for such k ≤ 6, and where q = ? ? for k ≥ 7. The number of edges is close to the lower bound of Ω( ) for the number of edges in a universal graph for the family of graphs with n vertices and maximum degree k. © 2010 Wiley Periodicals, Inc. Random Struct. Alg., 2010     

Merging percolation on Zd and classical random graphs: Phase transition

We study a random graph model which is a superposition of bond percolation on Z^d with parameter p, and a classical random graph G(n,c/n). We show that this model, being a homogeneous random graph, has a natural relation to the so‐called “rank 1 case” of inhomogeneous random graphs. This allows us to use the newly developed theory of inhomogeneous random graphs to describe the phase diagram on the set of parameters c ≥ 0 and 0 ≤ p < p_c, where p_c = p_c(d) is the critical probability for the bond percolation on Z^d. The phase transition is of second order as in the classical random graph. We find the scaled size of the largest connected component in the supercritical regime. We also provide a sharp upper bound for the largest connected component in the subcritical regime. The latter is a new result for inhomogeneous random graphs with unbounded kernels. © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2010     

The join of split graphs whose half-strong endomorphisms form a monoid

In this paper, the half-strong endomorphisms of the join of split graphs are investigated. We give the conditions under which the half-strong endomorphisms of the join of split graphs form a monoid.     

完全图删边子图的子刻画

In this paper, we show that some edges-deleted subgraphs of complete graph are determined by their spectrum with respect to the adjacency matrix as well as the Laplacian matrix.     

零维数等于1的单圈图

The nullity of a graph G is defined to be the multiplicity of the eigenvalue zero in its spectrum. In this paper we characterize the unicyclic graphs with nullity one in aspect of its graphical construction.     

On the chromatic number of random d-regular graphs

In this work we show that, for any fixed d, random d-regular graphs asymptotically almost surely can be coloured with k colours, where k is the smallest integer satisfying d<2(k−1)log(k−1). From previous lower bounds due to Molloy and Reed, this establishes the chromatic number to be asymptotically almost surely k−1 or k. If moreover d>(2k−3)log(k−1), then the value k−1 is discarded and thus the chromatic number is exactly determined. Hence we improve a recently announced result by Achlioptas and Moore in which the chromatic number was allowed to take the value k+1. Our proof applies the small subgraph conditioning method to the number of equitable k-colourings, where a colouring is equitable if the number of vertices of each colour is equal.     

Acyclic dominating partitions

Given a graph G=(V, E), let ${\mathcal{P}}$ be a partition of V. We say that ${\mathcal{P}}$ is dominating if, for each part P of ${\mathcal{P}}$, the set V\P is a dominating set in G (equivalently, if every vertex has a neighbor of a different part from its own). We say that ${\mathcal{P}}$ is acyclic if for any parts P, P′ of ${\mathcal{P}}$, the bipartite subgraph G[P, P′] consisting of the edges between P and P′ in ${\mathcal{P}}$ contains no cycles. The acyclic dominating number ad(G) of G is the least number of parts in any partition of V that is both acyclic and dominating; and we shall denote by ad(d) the maximum over all graphs G of maximum degree at most d of ad(G). In this article, we prove that ad(3)=2, which establishes a conjecture of P. Boiron, É. Sopena, and L. Vignal, DIMACS/DIMATIA Conference “Contemporary Trends in Discrete Mathematics”, 1997, pp. 1–10. For general d, we prove the upper bound ad(d)=O(dlnd) and a lower bound of ad(d)=Ω(d). © 2009 Wiley Periodicals, Inc. J Graph Theory 64: 292–311, 2010     

Star coloring planar graphs from small lists

A star coloring of a graph is a proper vertex‐coloring such that no path on four vertices is 2‐colored. We prove that the vertices of every planar graph of girth 6 (respectively 7, 8) can be star colored from lists of size 8 (respectively 7, 6). We give an example of a planar graph of girth 5 that requires 6 colors to star color. © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 324–337, 2010